import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        TreeNode root = new TreeNode(preorder[0]);
        int index = -1;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == preorder[0]) {
                index = i;
                break;
            }
        }

        root.left = index > 0 ? buildTree(Arrays.copyOfRange(preorder, 1, index + 1),
                Arrays.copyOfRange(inorder, 0, index)) : null; // 注意数组取部分
        root.right = index < len-1 ? buildTree(Arrays.copyOfRange(preorder, index + 1, len),
                Arrays.copyOfRange(inorder, index + 1, len)) : null;
        return root;
    }


}

/*运用map优化后*/
class Solution2 {
    private final Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        for (int i = 0; i < len; i++) {
            map.put(inorder[i], i);
        }
        return myBuildTree(preorder,0, len -1, inorder, 0, len -1);
    }
    public TreeNode myBuildTree(int[] preorder, int preStart, int preEnd, int[] inorder , int inStart, int inEnd) {
        TreeNode node = new TreeNode(preorder[preStart]);
        int index = map.get(preorder[preStart]);
        node.left = index > inStart ? myBuildTree(preorder, preStart+1,preStart+1 + index-1 - inStart,
                inorder, inStart, index-1) : null;
        node.right = index < inEnd ? myBuildTree(preorder, preEnd - inEnd + index +1, preEnd,
                inorder, index+1, inEnd) : null;
        return node;
    }
}
/*迭代待补充*/




class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
